<html>
    <head>
        <title>
            Graph Traversal.
        </title>
        <script type="text/javascript">

        <!--
            var compute = function(){
                console.log("start ..............");
                var graphs = getGraphs();
                graphs = sortGraphs(graphs)
                buildNodes_Edges(graphs);

                for (var i=0; i<graphs.length; i++){
                    console.log("Graph "+i+":");
                    bfs(graphs[i]);
                    checkGraph(graphs[i]);
                }

                console.log("..............  end.");
            };

            var sortGraphs = function(graphs){
                var list = [];
                for (var p in graphs)
                    list.push(graphs[p]);
                list.sort(function(a,b){return a.numberOfNodes-b.numberOfNodes;});
                return list;
            };

            var buildNodes_Edges = function(graphs){
                for (var i=0; i<graphs.length ; i++){
                    var graph = graphs[i];
                    graph.nodes = [];
                    var node;
                    for (var j=0 ; j<graph.numberOfNodes ; j++){
                        node = new Node(j);
                        graph.nodes.push(node);
                    }

                    graph.edges = [];
                    var edge;
                    var n0,n1;
                    for (var k=0 ; k<graph.connections.length ; k++){
                        var connection = graph.connections[k];
                        n0 = graph.nodes[connection[0]];
                        n1 = graph.nodes[connection[1]];

                        edge = new Edge(n0, n1);

                        n0.edges.push(edge);
                        n1.edges.push(edge);

                        graph.edges.push(edge);
                    }
                }
            };

            var bfs = function(graph){
                var queue = [];
                graph.nodes[0].visited = true;
                queue.push(graph.nodes[0]);

                var node, edge, neighbor;
                while (queue.length > 0) {
                    node = queue.pop();
                    for (var i=0 ; i<node.edges.length ; i++)
                    {
                        edge = node.edges[i];
                        if (!edge.traversed)
                        {
                            edge.traversed = !edge.traversed;
                            if (edge.n0 == node)
                                neighbor = edge.n1;
                            else
                                neighbor = edge.n0;

                            neighbor.visited = !neighbor.visited;
                            queue.splice(0, 0, neighbor);
                        }
                    }
                }
            }

            var checkGraph = function(graph){
                for (var i=0 ; i<graph.nodes.length ; i++){
                    var node = graph.nodes[i];
                    if (!node.visited){
                        throw new Error("Error : This node is not visited!");
                        return;
                    }
                }
                console.log("Ok!");
            };

            var getGraphs = function(){
                var graphs = [];
                var graph = {numberOfNodes:7, connections:[[0,1],[0,6],[1,2],[6,5],[3,2],[4,5]]};
                graphs.push(graph);
                graph = {numberOfNodes:6, connections:[[0,1],[0,3],[1,2],[3,5],[4,5]]};
                graphs.push(graph);
                graph = {numberOfNodes:7, connections:[[0,1],[0,6],[1,2],[6,5],[3,2],[4,5],[4,3]]};
                graphs.push(graph);
                graph = {numberOfNodes:9, connections:[[0,1],[0,6],[1,2],[6,5],[3,2],[4,5],[8,0],[6,7]]};
                graphs.push(graph);
                graph = {numberOfNodes:8, connections:[[0,1],[0,6],[1,2],[6,5],[3,2],[4,5],[0,7]]};
                graphs.push(graph);
                return graphs;
            };

            var Node = function(id){
                this.id = id;
                this.edges = [];
                this.visited = false;
            };

            var Edge = function(n0, n1){
                this.traversed = false;
                this.n0 = n0;
                this.n1 = n1;
            };

        -->
        </script>

    </head>

    <body id="myBody">
    <h3>
        Graph Traversal.
    </h3>
    <p>
            This page contains an implementation of Breadth First Search(BFS) for graph traversal.
            Go through these steps:
           <ol>
           <li> Click on the button.</li>
           <li> You see an error in Firebug console, set a breakpoint on the error (red dot), then re-run to halt on the error message .</li>
           <li> Locate the defect causes the error.</li>
           </ol>

     <b>Note:</b>  In this case, <i>lastChange</i> queries may take longer time, be patient.
        </p>

    <button id="reproducer" onclick="compute()">
      Traverse Graphs!
    </button>

  </body>

</html>